#include<vector>
using namespace std;
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cand = -1;
        int count = 0;
        for (int& num:nums) {
            if (cand == num)
                ++count;
            else if (--count < 0) {
                count = 1;
                cand = num;
            }
        }
        return cand;
    }
};